package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class CombinationSum2 {

    /**
     * DFS + 剪枝
     * DFS: 每次回退时判断target是否为0，如果为0说明这次搜索的路径有效，否则无效。
     * 剪枝：
     *  1. 先对数组进行排序，由题意可知数组中每个元素都大于1，所以当数组元素大于target时，就无须再比较了。
     *  2. 下一个节点的下标总是大于等于当前下标，这样可以避免因组合顺序不同导致的重复组合
     *  3. 路径回退后开始寻找新的下一个节点时，下一个节点要和当前节点的值不一样，这样就可以避免因不同下标但值相同导致的重复组合
     *
     * 注意:
     *  1. 所有数字（包括目标数）都是正整数。
     *  2. 解集不能包含重复的组合。
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        combination(candidates, target, 0, new LinkedList<>(), res);
        return res;
    }

    public void combination(int[] candidates, int target, int index, LinkedList<Integer> path, List<List<Integer>> res){
        if (target < 0){
            return;
        }
        if (target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; i++){
            int n = candidates[i];
            if (n > target){
                return;
            }
            path.push(n);
            combination(candidates, target - n, i + 1, path, res);
            path.pop();
            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]){
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        List<List<Integer>> lists = new CombinationSum2().combinationSum(candidates, target);
        PrintUtils.println(lists);

    }

}
